// Copyright (c) 2009 Christopher Keith (chris.keith@gmail.com)
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.

// Implement fast string lookups for anagrams, sets, etc.
// Uses nibble-lookups to handle counts as well as set-existence.
// Only the 2nd fastest... :(
// Fastest used straight bit-wise set lookups.

#include <iostream>
#include <fstream>
#include <exception>
#include <string>
#include <map>
#include <iomanip>
using namespace std;

#include "windows.h"
#include <direct.h>

class Utilities {
public:
  static string  getcwd();
  static unsigned long FileSize(ifstream& f);
};

string Utilities::getcwd() {
    const int   bufSize = 2000;
    char        buf[bufSize];
    char*       ret = _getcwd(buf, bufSize);
    if (ret != NULL) {
        return ret;
    }
    return "Error in getcwd";
}
unsigned long Utilities::FileSize(ifstream& f) {
  if (!f.good() || f.eof() || !f.is_open()) { return 0; }
  f.seekg(0, std::ios_base::beg);
  std::ifstream::pos_type begin_pos = f.tellg();
  f.seekg(0, std::ios_base::end);
  std::ifstream::pos_type end_pos = f.tellg();
  f.seekg(0, std::ios_base::beg);
  return (end_pos - begin_pos);
}

void    LongLongToInts(int tgt[], long long src) {
  for (int i = 0; i < 16; i++) {
    tgt[i] = (int)(((src >> (i * 4))) & 15);
  }
}
string  LongLongToNibbleString(long long v, int max) {
  string  s;
  int     counts[16];
  LongLongToInts(counts, v);
  for (int i = 0; i < max; i++) {
    if (counts[i] < 10) {
      s += " ";
    }
    char    buf[128];
    _itoa_s(counts[i], buf, 127, 10);
    s += buf;
  }
  return s;
}
//--------//--------//--------//--------//--------//--------//--------//--------//--------
class Timer {
public:
  Timer(const char * msg) : mStart(GetTickCount()), mMessage(msg) { }
  ~Timer();
private:
  long   mStart;
  const char  *mMessage;
};
Timer::~Timer() {
  cout << mMessage << " in " << GetTickCount() - mStart << " milliseconds." << endl;
}
//--------//--------//--------//--------//--------//--------//--------//--------//--------
class CharCounts {
public:
          CharCounts();
  bool    operator<(const CharCounts& other) const;
  void    Init(char* w);
  int     GetCharCount(char c);
  string  AsString() const;
  void    AccumulateStats(const CharCounts& wb, char* wordsWithMax[], char* word);
  bool    SameSet(const CharCounts& other) const;
  bool    SuperSet(const CharCounts& other) const;
  bool    SameBag(const CharCounts& other) const;
  bool    SuperBag(const CharCounts& other) const;
  bool    Similar(const CharCounts& other, int k) const;
  friend ostream& operator<<(ostream& ostr, const CharCounts& a);
private:
  static const unsigned int mMaxChars = 26;
  unsigned long long  mBit0;
  unsigned long long  mBit1;
  int     mCounts[mMaxChars];   // cached for performance

  void    CountsToBits();
  int     CharToIndex(const char c) { return tolower(c) - (int)'a'; }
};

ostream& operator<<(ostream& ostr, const CharCounts& a) {
  ostr << a.AsString();
  return ostr;
}
CharCounts::CharCounts() {
  mBit0 = 0;
  mBit1 = 0;
  memset(mCounts, 0, sizeof(int) * mMaxChars);
}
bool CharCounts::operator<(const CharCounts& other) const {
  if (mBit0 < other.mBit0) {
    return true;
  }
  if (mBit0 > other.mBit0) {
    return false;
  }
  return (mBit1 < other.mBit1);
}
void CharCounts::CountsToBits() {
  mBit0 = 0;
  mBit1 = 0;
  for (int i = 0; i < 16; i++ ) {
    mBit0 |= (((long long)mCounts[i]) << (i * 4));
  }
  for (int i = 16; i < mMaxChars; i++ ) {
    mBit1 |= (((long long)mCounts[i]) << ((i - 16) * 4));
  }
}
void CharCounts::Init(char* w) {
  while (*w) {
    if (isalpha(*w)) {
      mCounts[ CharToIndex(*w) ]++;
    }
    w++;
  }
  CountsToBits();
}
inline bool CharCounts::SameSet(const CharCounts& other) const {
  for (int i = 0; i < mMaxChars; i++) {
    if ((mCounts[i] == 0) != (other.mCounts[i] == 0)) {
      return false;
    }
  }
  return true;
}
inline bool CharCounts::SuperSet(const CharCounts& other) const {
  for (int i = 0; i < mMaxChars; i++) {
    if ((mCounts[i] == 0) && (other.mCounts[i] != 0)) {
      return false;
    }
  }
  return true;
}
inline bool CharCounts::SameBag(const CharCounts& other) const {
  for (int i = 0; i < mMaxChars; i++) {
    if (mCounts[i] != other.mCounts[i]) {
      return false;
    }
  }
  return true;
}
inline bool CharCounts::SuperBag(const CharCounts& other) const {
  for (int i = 0; i < mMaxChars; i++) {
    if (mCounts[i] < other.mCounts[i]) {
      return false;
    }
  }
  return true;
}
inline bool CharCounts::Similar(const CharCounts& other, int k) const {
  int   count = 0;
  for (int i = 0; i < mMaxChars; i++) {
    count += min(mCounts[i], other.mCounts[i]);
    if (count > k) {
      return false;
    }
  }
  return count == k;
}
int CharCounts::GetCharCount(char c) {
  if ( ! isalpha(c)) {
    return 0;
  }
  return mCounts[ CharToIndex(c) ];
}
string CharCounts::AsString() const {
  return LongLongToNibbleString(mBit0, 16) + LongLongToNibbleString(mBit1, 10);
}
void CharCounts::AccumulateStats(const CharCounts& other, char* wordsWithMax[], char* word) {
  for (int i = 0; i < mMaxChars; i++) {
    if (mCounts[i] < other.mCounts[i]) {
      mCounts[i] = other.mCounts[i];
      wordsWithMax[i] = word;
    }
  }
  CountsToBits();
}
struct ltCharCounts {
  bool operator()(const CharCounts& s1, const CharCounts& s2) const {
    return s1 < s2;
  }
};

//--------//--------//--------//--------//--------//--------//--------//--------//--------
typedef multimap<CharCounts, const char *, ltCharCounts> wordSet;
typedef pair<CharCounts, const char*> wordData;

class DictionaryPlusPlus {
public:
        DictionaryPlusPlus();
  void  Initialize(string fn);
  void  InitializeFromArray(char ** array, int length);
  void  DumpN(int n);
  void  CreateAnagramFile();
  void  DumpStats();
  int   GetSamebag(string& output, string& word) const;
  int   GetSameset(string& output, string& word) const;
  int   GetSubset(string& output, string& word) const;
  int   GetSubbag(string& output, string& word) const;
  int   GetSuperset(string& output, string& word) const;
  int   GetSuperbag(string& output, string& word) const;
  int   GetSimilar(string& output, string& word, int i) const;
private:
  enum eSetType {
    eSameSet, eSuperSet, eSubSet, eSuperBag, eSubBag, eSimilar
  };

  char            *mInFileBuf;
  unsigned long   mInFileSize;
  static const unsigned int  mMaxWords = 200000;
  CharCounts      mCharCounts[mMaxWords];
  wordSet         mMapByBag;
  wordData        mWordData[mMaxWords];
  CharCounts      mMaxCC;

  wordSet::const_iterator  GetBag(string& output, const CharCounts& c, int* count) const;
  int             GetSet(string& output, const CharCounts& c, eSetType t, int k = 0) const;
};

DictionaryPlusPlus::DictionaryPlusPlus()
: mInFileBuf(NULL),
  mInFileSize(0) {
}

void DictionaryPlusPlus::InitializeFromArray(char ** array, int length) {
	for (int i = 0; i < length; i++) {
      mCharCounts[i].Init(array[i]);
      mMapByBag.insert(wordData(mCharCounts[i], array[i]));
	}
}
void DictionaryPlusPlus::Initialize(string fn) {
  ifstream    fstr;
  fstr.open(fn.c_str(), ios::in | ios::binary);
  mInFileSize = Utilities::FileSize(fstr);
  if (mInFileSize == 0) {
    string err = "Error! Filesize is zero: ";
    err += fn;
    exception* e = new exception(err.c_str());
    throw e;
  }
  mInFileBuf = new char[mInFileSize];
  fstr.read(mInFileBuf, mInFileSize);
  if (fstr.fail()) {
    string err = "Error! fstr.fail: ";
    err += fn;
    exception* e = new exception(err.c_str());
    throw e;
  }
  fstr.close();

  Timer t("Built multimap");
  unsigned long nWords = 0;
  char* curWord = mInFileBuf;
  for (unsigned long i = 0; i < mInFileSize; i++) {
    // ONLY works with DOS-style text files...
    if (mInFileBuf[i] == '\r') {
      if (nWords > mMaxWords) {
        string err = "Error! too many words in: ";
        err += fn;
        exception* e = new exception(err.c_str());
        throw e;
      }
      mInFileBuf[i] = '\0';
      mCharCounts[nWords].Init(curWord);
      mWordData[nWords].first = mCharCounts[nWords];
      mWordData[nWords].second = curWord;
      mMapByBag.insert(mWordData[nWords]);
      nWords++;
    }
    if (mInFileBuf[i] == '\n') {
      curWord = &mInFileBuf[i + 1];
    }
  }
  cout << "Found " << nWords << " words." << endl;
}
void DictionaryPlusPlus::DumpN(int n) {
  cout << "       a b c d e f g h i j k l m n o p q r s t u v w x y z" << endl;
  wordSet::iterator it = mMapByBag.begin();
  while (it != mMapByBag.end()) {
      cout << "  [" << mMapByBag.count((*it).first) << ", "
                    << (*it).first << ", "
                    << (*it).second << "]" << endl;
      if (n-- <= 0) {
        break;
      }
    it++;
  }
}
wordSet::const_iterator DictionaryPlusPlus::GetBag(string& output, const CharCounts& c, int* count) const {
  pair<wordSet::const_iterator, wordSet::const_iterator> p = mMapByBag.equal_range(c);
  while (p.first != p.second) {
    output += p.first->second;
    output += " ";
    p.first++;
    (*count)++;
  }
  return p.second;
}
int DictionaryPlusPlus::GetSet(string& output, const CharCounts& c, eSetType t, int k) const {
  bool  pass;
  int   count = 0;
  wordSet::const_iterator it = mMapByBag.begin();
  while (it != mMapByBag.end()) {
    switch (t) {
      case eSameSet  : pass = c.SameSet((*it).first); break;
      case eSubSet   : pass = c.SuperSet((*it).first); break;
      case eSuperSet : pass = (*it).first.SuperSet(c); break;
      case eSubBag   : pass = c.SuperBag((*it).first); break;
      case eSuperBag : pass = (*it).first.SuperBag(c); break;
      case eSimilar  : pass = (*it).first.Similar(c, k); break;
      default     : cout << "Bad type in DictionaryPlusPlus::GetSet" << endl; pass = false; break;
    }
    if (pass) {
      it = GetBag(output, (*it).first, &count);
      output += "\n";
    } else {
      it++;
    }
  }
  return count;
}
int DictionaryPlusPlus::GetSamebag(string& output, string& word) const {
  CharCounts c;
  c.Init((char *)word.c_str());
  int count = 0;
  GetBag(output, c, &count);
  return count;
}
int DictionaryPlusPlus::GetSameset(string& output, string& word) const {
  CharCounts c;
  c.Init((char *)word.c_str());
  return GetSet(output, c, eSameSet);
}
int DictionaryPlusPlus::GetSubset(string& output, string& word) const {
  CharCounts c;
  c.Init((char *)word.c_str());
  return GetSet(output, c, eSubSet);
}
int DictionaryPlusPlus::GetSubbag(string& output, string& word) const {
  // other options:
  // find char pattern, if not there, temporarily insert it into map
  // find next char pattern, if not there, temporarily insert it into map
  // use range...

// or
  // use upper_bound, lower_bound?
  CharCounts c;
  c.Init((char *)word.c_str());
  return GetSet(output, c, eSubBag);
}
int DictionaryPlusPlus::GetSuperset(string& output, string& word) const {
  CharCounts c;
  c.Init((char *)word.c_str());
  return GetSet(output, c, eSuperSet);
}
int DictionaryPlusPlus::GetSuperbag(string& output, string& word) const {
  CharCounts c;
  c.Init((char *)word.c_str());
  return GetSet(output, c, eSuperBag);
}
int DictionaryPlusPlus::GetSimilar(string& output, string& word, int i) const {
  CharCounts c;
  c.Init((char *)word.c_str());
  return GetSet(output, c, eSimilar, i);
}
void DictionaryPlusPlus::CreateAnagramFile() {
  Timer       t("Created anagram file");
  string      s = "";
  s.reserve(2500000);
  size_t      maxAnagrams = 0;
  wordSet::const_iterator it = mMapByBag.begin();
  while (it != mMapByBag.end()) {
    size_t   c = mMapByBag.count((*it).first);
    if (c == 1) {
      it++;
    } else {
      if (maxAnagrams < c) {
          maxAnagrams = c;
          mMaxCC = (*it).first;
      }
      int count;
      it = GetBag(s, (*it).first, &count);
      s += "\n";
    }
  }
  ofstream    fstr;
  fstr.open("anagrams.txt", ios::out | ios::binary);
  fstr.write(s.c_str(), (std::streamsize)s.size());
  fstr.close();
  cout << endl;
}
void DictionaryPlusPlus::DumpStats() {
  CharCounts   maxCounts;
  char*        wordsWithMax[26];
  memset(wordsWithMax, 0, 26 * sizeof(int));
  wordSet::iterator it = mMapByBag.begin();
  while (it != mMapByBag.end()) {
    CharCounts  wb = (*it).first;
    maxCounts.AccumulateStats(wb, wordsWithMax, (char *)(*it).second);
    it++;
  }
  cout << endl;
  for (int i = 0; i < 26; i++) {
    cout << (char)(i + 'a') << " " << setw(2) << maxCounts.GetCharCount((char)(i + 'a')) << " ";
    cout << ((wordsWithMax[i] == NULL) ? "[NULL]" : wordsWithMax[i]) << endl;
  }
  cout << endl << "Max anagrams: " << mMapByBag.count(mMaxCC) << endl;
  pair<wordSet::iterator, wordSet::iterator>  its = mMapByBag.equal_range(mMaxCC);
  for (it = its.first; it != its.second; it++) {
    cout << (*it).second << "\t";
  }
  cout << endl << endl;
}

//--------//--------//--------//--------//--------//--------//--------//--------//--------
class FinalAssignmentTester {
public:
          FinalAssignmentTester() {}
  void	  Run();
private:
  DictionaryPlusPlus*  mDict;

  string  GetInputFile();
  void    RunQuickTest();
  void    AutoLoadWordFile();
  void    RunAutoTest();
  void    T1(bool doSuper);
  void    T2();

  void    Interact();
  char    ShowMenu();
  void    PerformAction(char c);
  void    Sameset(string& s);
  void    Samebag(string& s);
  void    Subset(string& s);
  void    Subbag(string& s);
  void    Superset(string& s);
  void    Superbag(string& s);
  void    Similar(string& s);
  string  GetWord();
  void    PrintResult(int c, string& s);
};

void FinalAssignmentTester::PrintResult(int c, string& s) {
  cout << "Matches found: " << c << endl;
  if (s.length() < 200) {
    cout << s;
  } else {
    cout << s.substr(0, 200) << "...";
  }
  cout << endl;
}
string FinalAssignmentTester::GetWord() {
  cout << "Enter word: ";
  char    line[2048];
  cin.getline(line, 2048);
  string  s(line);
  return s;
}
void FinalAssignmentTester::Sameset(string& s) {
  string  t;
  Timer   timer("Operation completed");
  int c = mDict->GetSameset(t, s);
  PrintResult(c, t);
}
void FinalAssignmentTester::Samebag(string& s) {
  string  t;
  Timer   timer("Operation completed");
  int c = mDict->GetSamebag(t, s);
  PrintResult(c, t);
}
void FinalAssignmentTester::Subset(string& s) {
  string  t;
  Timer   timer("Operation completed");
  int c = mDict->GetSubset(t, s);
  PrintResult(c, t);
}
void FinalAssignmentTester::Subbag(string& s) {
  string  t;
  Timer   timer("Operation completed");
  int c = mDict->GetSubbag(t, s);
  PrintResult(c, t);
}
void FinalAssignmentTester::Superset(string& s) {
  string  t;
  Timer   timer("Operation completed");
  int c = mDict->GetSuperset(t, s);
  PrintResult(c, t);
}
void FinalAssignmentTester::Superbag(string& s) {
  string  t;
  Timer   timer("Operation completed");
  int c = mDict->GetSuperbag(t, s);
  PrintResult(c, t);
}
void FinalAssignmentTester::Similar(string& s) {
  cout << "Enter number of chars to match: ";
  int i;
  cin >> i;
  string  t;
  Timer   timer("Operation completed");
  int c = mDict->GetSimilar(t, s, i);
  PrintResult(c, t);
}
char FinalAssignmentTester::ShowMenu() {
  cout << endl;
  cout << "a - same-set words" << endl;
  cout << "b - same-bag words" << endl;
  cout << "c - subset words" << endl;
  cout << "d - subbag words" << endl;
  cout << "e - superset words" << endl;
  cout << "f - superbag words" << endl;
  cout << "g - similar words" << endl;
  cout << "r - run automated test" << endl;
  cout << "s - dump stats" << endl;
  cout << "q - quit" << endl;
  cout << "Enter <commandCharacter>: ";
  char line[256];
  cin.getline(line, 256);
  return line[0];
}
void FinalAssignmentTester::PerformAction(char c) {
  switch (c) {
    case 'a': Sameset(GetWord()); break;
    case 'b': Samebag(GetWord()); break;
    case 'c': Subset(GetWord()); break;
    case 'd': Subbag(GetWord()); break;
    case 'e': Superset(GetWord()); break;
    case 'f': Superbag(GetWord()); break;
    case 'g': Similar(GetWord()); break;
    case 'r': RunAutoTest(); break;
    case 's': mDict->DumpStats(); break;
    default: cout << "Unknown command: " << c << endl; break;
  }
}
void FinalAssignmentTester::Interact() {
  char c;
  while ((c = ShowMenu()) != 'q') {
    PerformAction(c);
  }
}
string FinalAssignmentTester::GetInputFile() {
  cout << "Current directory is: " << endl;
  cout << Utilities::getcwd() << endl << endl;
  cout << "Specify directory containing words.txt file ('.' for current directory): ";
  char    dir[1024];
  cin.getline(dir, 1023);
  string  fn = dir;
  fn += "\\words.txt";
  return fn;
}
void FinalAssignmentTester::AutoLoadWordFile() {
  cout << "Looking for words.txt file in directory: " << endl;
  cout << Utilities::getcwd() << endl << endl;
  mDict = new DictionaryPlusPlus();
  mDict->Initialize(".\\words.txt");
  mDict->CreateAnagramFile();
}
void FinalAssignmentTester::T2() {
  mDict = new DictionaryPlusPlus();
  char*	t[] = { "bat", "cat" };
  mDict->InitializeFromArray(t, sizeof(t) / sizeof(char*));
  mDict->DumpN(10);
  string s = "";
  string u = "bat";
  mDict->GetSimilar(s, u, 2);
  cout << "Similar of 'bat', 2:" << endl << s << endl;
}
void FinalAssignmentTester::T1(bool doSuper) {
  string s;
  string u = "star";
  mDict->GetSameset(s, u);
  cout << "Sameset of 'star':" << endl << s << endl;
  s = "";
  u = "sta";
  mDict->GetSubset(s, u);
  cout << "Subset of 'sta':" << endl << s << endl;
  s = "";
  mDict->GetSubbag(s, u);
  cout << "Subbag of 'sta':" << endl << s << endl;
  if (doSuper) {
    s = "";
    u = "star";
    mDict->GetSuperbag(s, u);
    cout << "Superbag of 'star':" << endl << s << endl;
    s = "";
    u = "sta";
    mDict->GetSuperset(s, u);
    cout << "Superset of 'sta':" << endl << s << endl;
    s = "";
    mDict->GetSimilar(s, u, 3);
    cout << "Similar of 'sta', 3:" << endl << s << endl;
  }
}
void FinalAssignmentTester::RunQuickTest() {
  mDict = new DictionaryPlusPlus();
  char*	t[] = { "star", "stars", "starr", "starx", "sta", "a" };
  mDict->InitializeFromArray(t, sizeof(t) / sizeof(char*));
  mDict->DumpN(10);
  mDict->DumpStats();
  T1(true);
  T2();
}
void FinalAssignmentTester::RunAutoTest() {
  mDict->DumpN(10);
  mDict->DumpStats();
  T1(false);
}
void FinalAssignmentTester::Run() {
  try {
    // RunQuickTest();
	  AutoLoadWordFile();
	  Interact();
  } catch (exception* e) {
    cout << e->what() << endl;
    char c;
    cin.get(c);
  }
}
//--------//--------//--------//--------//--------//--------//--------//--------//--------
int main() {
  FinalAssignmentTester* f = new FinalAssignmentTester();
  f->Run();
  return 0;
}
